A B-tree is a type of a search tree that supports insertion, lookup, deletion, and other types of operations such that data access operations with respect to a storage infrastructure are made more efficient. A B-tree is made up of a tree of nodes, including a root node, intermediate nodes, and leaf nodes. Values associated with keys are stored at the leaf nodes. The internal nodes (non-leaf nodes) of the B-tree contain pointers to lower-level nodes. A search for a particular key performed with a B-tree starts at the root node, and the B-tree is traversed from top to bottom. Once the leaf node with the particular key is found, then the value associated with the key can be retrieved.
Various proposals for distributing B-trees across a distributed system have been made to enhance the efficiency of B-trees. However, such proposals suffer from various drawbacks, including one or more of lack of fault tolerance, reduced performance due to bottlenecks at some nodes of the B-trees, and others.